package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20240818;

public class leetcode3259 {
    /**
     * 参考灵茶山艾府思路：
     * 方法一：
     * 1、寻找子问题
     * （1）从右往左思考，主要是为了方便把递归翻译成递推
     * （2）动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。
     * 在做题时，可根据题目要求，选择适合题目的一种来思考。本题用到的是「选或不选」：
     * 如果当前选了 a 中的元素，接下来要么继续选 a 中的元素，
     * 要么不继续选 a 中的元素，也就是选 b 中的元素
     *
     * 2、状态定义与状态转移方程
     * （1）为了方便实现，把a和b加到一个长为2的二维数组中
     * （2）dfs(i,j)=max(dfs(i-1,j),dfs(i-2,j^1))+c[i][j]
     * 3、引入memo进行记忆化搜索
     *
     * 方法二：递推
     * 1、状态转移方程：f[i+2][j]=max(f[i+1][j],f[i][j^1])+c[j][i]
     * @param energyDrinkA
     * @param energyDrinkB
     * @return
     */

    // 方法一
    public long maxEneryBoost(int[] energyDrinkA,int[] energyDrinkB){
        int n=energyDrinkA.length;
        int[][] dp={energyDrinkA,energyDrinkB};
        long[][] memo=new long[n][2];
        return Math.max(dfs(n-1,0,dp,memo),dfs(n-1,1,dp,memo));
    }

    private long dfs(int i,int j,int[][] dp,long[][] memo){
        if(i<0){
            return 0;
        }
        if(memo[i][j]>0){// 表示之前计算过
            return memo[i][j];
        }
        return memo[i][j]=Math.max(dfs(i-1,j,dp,memo),dfs(i-2,j^1,dp,memo))+dp[j][i];
    }

//    // 方法二
//    public long maxEneryBoost(int[] energyDrinkA,int[] energyDrinkB){
//        int n=energyDrinkA.length;
//        long[][] dp=new long[n+2][2];
//        for(int i=0;i<n;i++){
//            dp[i+2][0]=Math.max(dp[i+1][0],dp[i][1])+energyDrinkA[i];
//            dp[i+2][1]=Math.max(dp[i+1][1],dp[i][0])+energyDrinkB[i];
//        }
//        return Math.max(dp[n+1][0],dp[n+1][1]);
//    }

}
